#include<bits/stdc++.h>
using namespace std;

// class Solution {
// public:
//     int b_search(vector<int>& nums, int target){
//         int low = 0, high = nums.size() - 1, mid;
//         while(low < high){
//             mid = low + (high - low) / 2;
//             if(nums[mid] == target) return mid;
//             else if(nums[mid] < target) low = mid + 1;
//             else high = mid;
//         }
//         return -1;
//     }
//     vector<int> twoSum(vector<int>& numbers, int target) {
//         vector<int>ans;
//         for(int i = 0; i < numbers.size(); i++){
//             int temp = b_search(numbers, target - numbers[i]);
//             if(temp == -1)continue;
//             ans.emplace_back(i);
//             ans.emplace_back(temp);
//         }
//         return ans;
//     }
// };
// /**
//  * @brief 2022.3.5
//  * 遍历 + 二分写法 O(nlogn)
//  * 
//  */


class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int>ans;
        int i = 0, j = numbers.size() - 1;
        while(i < j){
            if(numbers[i] + numbers[j] == target){
                ans.emplace_back(i + 1);
                ans.emplace_back(j + 1);
                break;
            }
            else if(numbers[i] + numbers[j] < target)i++;
            else j--;
        }
        return ans;
    }
};

/**
 * @brief 2022.3.5
 * 双指针 O(n)
 */